package com.aqie.easy.array;

/**
 * 605 种花问题 todo
 */
public class CanPlaceFlowers {
    /**
     * 1, 3ms
     * 判断的标准是当前位置为0，且前一位置为0或其下标为-1，
     * 且后一位置为0或其下标为flowerbed.length。
     * 若判断为真，则修改flowerbed[]数组当前位置为1，n--。最后若n<=0,则能种下所有花。
     *
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0
                    && (i - 1 == -1 || flowerbed[i - 1] == 0)
                    && (i + 1 == flowerbed.length || flowerbed[i + 1] == 0)) {
                n--;
                flowerbed[i] = 1;
            }
        }
        return n <= 0;
    }

    /**
     * 2, 2ms
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers2(int[] flowerbed, int n) {
        int canInsertCounts = 0;

        for (int i = 0; i < flowerbed.length;i++) {
            if(flowerbed[i] == 1){
                i++;
            }

            else if(i == flowerbed.length-1 || flowerbed[i+1] == 0){
                flowerbed[i] = 1;
                i++;
                canInsertCounts++;
            }
        }

        return canInsertCounts >= n;
    }

    /**
     * 3, 7ms
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers3(int[] flowerbed, int n) {
        int pre=-2,cur,cnt=0;
        for(int i=0;i<flowerbed.length;i++)
        {
            if (flowerbed[i] != 0) {
                if(flowerbed[i]==1)
                {
                    cur=i;
                    cnt+=Math.max((cur-pre-2)/2,0);
                    pre=i;
                }
            }
        }
        cnt+=(flowerbed.length-pre-1)/2;
        return cnt>=n;
    }
}
